1. Field of the Invention
This invention relates to block ciphers. More particularly, this invention relates to improving the security of block ciphers using cipher concatenation in combination with a random number generator.
2. Description of the Related Art
Various block ciphers are known and are used to encrypt (and decrypt) data. Block ciphers are described in detail in Bruce Schneier, xe2x80x9cApplied Cryptographyxe2x80x9d Second Edition, 1996, which is incorporated herein by reference. Block ciphers operate on blocks of plaintext and ciphertext, usually of 64 bits but sometimes longer. Block ciphers have the property that, using the same key, the same plaintext block will always encrypt to the same ciphertext block. Typical block ciphers currently use 128-bit keys although shorter and longer keys can be used.
It is generally the case that the greater the key length for a particular cipher, the stronger the cipher. In some ways this is simply related to the number of keys which need to be tried in order to decipher a message. A key length of k means that at most 2k possible keys exist and must be tried in order to decipher a message using an exhaustive key search. In fact, for an n-bit block cipher with a k-bit key, given a small number e.g., ┌(k+4)/n┐ of plaintext-ciphertext pairs encrypted under the key K, K can be recovered by exhaustive key search in an expected time on the order of 2kxe2x88x921 operations.
Cipher concatenation or combined (e.g., chained) block ciphers are also known, however such combinations do not necessarily add to security since they may not effectively increase the key length. For example, double encryption with two separate 128-bit keys does not provide effective 256-bit key security against known attacks.
One of the reasons that cascaded or multiple chained block ciphers may not be any stronger than a single block cipher is that chains are vulnerable to various attacks which do not require brute force attempts using all keys. A naxc3xafve exhaustive attack on all key pairs in double DES uses on the order of 2112 operations, whereas a non-naxc3xafve, so-called meet-in-the-middle attack on the same combination requires only on the order of 256 operations. Various other combinations are known, including, e.g., triple encryption with two keys, and other variants on triple encryption.
One other known way to combine multiple blocks is to use two algorithms (and two independent keys). Using this approach, first generate a random-bit string, R, the same size as the message M. Then encrypt R with the first algorithm (and the first key) and then encrypt M⊕R (the exclusive-or combination of M and R) with the second algorithm (and the second key). The ciphertext is the combined result of the two encryptions and is at least as strong as the stronger of the two encryption algorithms.
Assuming that the random string is indeed random, this approach encrypts M with a one-time pad and then encrypts both the pad and the encrypted message with each of the two algorithms, respectively. Since both algorithms are required to reconstruct M, a cryptanalyst must break both. This method can be extended to multiple algorithms.
Combining multiple ciphers can have a problem in that the combination is potentially weakened if one of the component ciphers is compromised. Further, the combination may be only as strong as only one of the elements in the combination.
It is desirable to produce block ciphers with arbitrarily long key length so as to increase their security. It is also desirable to produce such block ciphers from existing, already accepted block ciphers as components. By using existing block ciphers as components, there is already a built up trust in the components.
This invention solves these and other problems by providing a combination block cipher with an effective key length greater than that of its components.
This invention increases the security provided by any single block cipher by providing encryption of an input stream by at least two different block ciphers. To add to the security, a one-time pad in the form of a random data stream, is combined with an encrypted form of the input stream before it is encrypted by the second block cipher.
In one aspect, this invention is an encryption device which has a random number generator and three block cipher mechanisms. The first block cipher mechanism takes a plaintext input and produces a first enciphered output based on the plaintext and on a first key. An exclusive-or mechanism takes as input the first enciphered output from the first block cipher and the output of the random number generator and produces a combined output. The second block cipher mechanism takes as input the output of the exclusive-or mechanism and produces a second enciphered output based on the output of the exclusive-or mechanism and on a second key. The third block cipher mechanism takes as input the output of the random number generator and produces a third enciphered output based on the output of the random number generator and on a third key. The first and second block cipher mechanisms differ from each other, with one preferably being the IDEA block cipher, and the other preferably being the Blowfish block cipher.
Preferably the first and third block cipher mechanisms are Blowfish block ciphers and the second block cipher is the IDEA block cipher. The plaintext input is preferably a sequence of 64-bit values and the output of the random number generator is a sequence of 64-bit random values. Preferably the random number generator is a true random number generator.
In another aspect, this invention is the decryption device corresponding to the encryption device.
This invention""s combination of block ciphers with random numbers has a number of advantages, including:
Cryptanalysis based on known characteristics of the plaintext is impossible.
The effective key length is the sum of key lengths used in BC1 and BC2 (256-bits in the preferred scheme).
Failure (such as discovery of a backdoor) of any of the two block cipher kinds used still leaves the 128-bit security of the other intact.
The same plaintext block never encrypts to the identical ciphertext block, and yet every ciphertext block is independent from any other ciphertext block.